
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {
    private int[][] edges;
    private ArrayList<String> arrayList;
    private int unmber;
    private boolean[] isvisity;
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String[] arr={"A","B","C","D","E"};
        graph.add(arr);

        graph.inserEdge(0,1,1);
        graph.inserEdge(0,2,1);
        graph.inserEdge(1,2,1);
        graph.inserEdge(1,3,1);
        graph.inserEdge(1,4,1);

        graph.getEdge();
        //graph.dfs();
        graph.bfs();

    }
    public Graph(int n){
        arrayList=new ArrayList<String>(n);
        edges=new int[n][n];
        unmber=0;
        isvisity=new boolean[n];
    }
    public void add(String[] strings){
        for (String str:strings) {
            arrayList.add(str);
        }
    }
    public int getunmber(){
        return unmber;
    }

    public String getvalueByIndex(int i){
        return arrayList.get(i);
    }
    public int getInserEdge(int v1,int v2){
        return edges[v1][v2];
    }
    public int getsize(){
        return arrayList.size();
    }
    public void inserEdge(int v1,int v2,int wight){
        edges[v1][v2]=wight;
        edges[v2][v1]=wight;
        unmber++;
    }

    public int getFirstOrder(int index){//返回第一个邻接点
        for (int i = 0; i < arrayList.size(); i++) {
            if (edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }

    public int getNextOrder(int v1,int v2){//返回当前结点的下一个邻接点
        for (int i = v2+1; i < arrayList.size(); i++) {
            if (edges[v1][i]>0){
                return i;
            }
        }
        return -1;
    }

    public void dfs(boolean[] isvisity,int i){//深度遍历
        System.out.print(getvalueByIndex(i)+"->");
        isvisity[i]=true;//遍历过
        int w=getFirstOrder(i);//获得第一个邻接点
        while (w!=-1){
            if (!isvisity[i]){//如果为true就遍历该节点
                dfs(isvisity,w);
            }
            w=getNextOrder(i,w);
        }
    }
    public void dfs(){//重载，遍历全部结点
        for (int i = 0; i < getsize(); i++) {
            if (!isvisity[i]){
                dfs(isvisity,i);
            }
        }
    }

    public void bfs(boolean[] isvisity,int i){
        int w;
        int u;
        System.out.print(getvalueByIndex(i)+"->");
        LinkedList linkedList = new LinkedList();
        isvisity[i]=true;//访问过
        linkedList.addLast(i);
        while (!linkedList.isEmpty()){
            u=(Integer) linkedList.removeFirst();
            w=getFirstOrder(u);
            while (w!=-1){
                if (!isvisity[w]) {
                    System.out.print(getvalueByIndex(w) + "->");
                    isvisity[w]=true;
                    linkedList.addLast(w);
                }
                w=getNextOrder(u,w);
            }
        }

    }
    public void bfs(){//重载，遍历全部结点
        for (int i = 0; i < getsize(); i++) {
            if (!isvisity[i]){
                bfs(isvisity,i);
            }
        }
    }

    public void getEdge(){
        for (int[] Edge:edges) {
            System.out.println(Arrays.toString(Edge));
        }
    }

}
